With a multipath transmission medium, the reciprocal of the allocated transmission bandwidth B is equal to resolution of echoes “perceived” by the system (δτ≅1/B). These echoes (delay and complex amplitude) are generated by waves reflected and diffracted by obstacles near the transmitter-receiver axis. They define coefficients of the impulse response of the propagation channel, which filters the communication signal within the bandwidth of the system. In broadband transmission with a bandwidth B (where B>channel coherence bandwidth), a small-size interleaver reduces to the scale of a few symbols the correlation of data items caused by the frequency-selective nature of the propagation channel. In narrowband transmission (where B<channel coherence bandwidth), correlation between data items is linked to narrowband variations of the radio-frequency field or ideal low-pass filtering of the data. Interleaving the transmitted data over a period greater than the channel coherence time enables decorrelation of data items at the receiver, after de-interleaving, and dissemination of data with a low signal-to-noise ratio. This increases the efficiency of the decision circuits in a digital transmission system receiver.
An interleaving law I(k) for a block of size K specifies the order in which an input data sequence formed by K data items indexed by an index k varying from 0 to K−1 must be read at the output. Let X(k) denote an input sequence of an interleaver with interleaving law I(k). Let Y(k) denote the output sequence of the interleaver. Then Y(k)=X(I(k)): the kth data item of the interleaved sequence having the position index k−1 corresponds to the data item of index I(k−1) of the input sequence X(0), . . . , X(K−1). The interleaving law I(k) is a one-to-one function that has values in the space S={0, . . . , K−1}. The interleaving spreading is defined as the smallest distance after interleaving between two position indices associated with two input data items X(k) and X(k+s) separated by s−1 data items. The interleaving spreading is given by the equation ΔIeff(s)=Mink,kεS|I(k+s)−I(k)|. The function |X| gives the absolute value of X.
The input data items to be interleaved and the interleaved output data items are represented in the remainder of this document only by their index k, unless otherwise indicated.
The invention is more particularly concerned with block interleaving techniques, i.e. interleaving techniques for which each block of data of size K is interleaved independently of any other block; here, the index k varies from 0 to K−1.
Some of these techniques are more specifically intended to combat fast fading and some are more specifically intended to improve the decoding circuits, in particular those for turbo-codes.
Interleaving algorithms for turbo-codes include relative prime (RP) interleavers described in particular in the paper by S. Crozier and P. Guinand, “High-Performance Low-Memory Interleaver Banks for Turbo-Codes”, Proceedings of the 54th IEEE Vehicular Technology Conference (VTC 2001 Fall), Atlantic City, N.J., USA, pp. 2394-2398, Oct. 7-11, 2001.
RP algorithms were originally designed to generate interleaving matrices internal to turbo-codes. These algorithms, which are block interleaving algorithms with a block size K, yield a particular interleaving spreading between two interleaved data items. They are known for their property of relatively high interleaving spreading on relatively small block sizes. However, on large blocks, high interleaving spreading requirement involves a large number of non-interleaved data items inserted into a periodic structure. These algorithms generate an interleaving law defined by two parameters s and d and by a modulo K operation. The parameter s is a shift on the first data item and the parameter d is the distance between two successive data items after interleaving; d sets the value of the interleaving spreading between two successive interleaved data items and must be prime relative to K. In some circumstances these algorithms preserve a pattern of size p. The advantage of this property is that it lightens the infrastructure of a multichannel interleaving system and addresses specific constraints associated with overall optimization of the transmission system.
Preserving a data distribution pattern corresponding to p streams of multiplexed data presupposes that the parameter p is a sub-multiple of the block size K to be interleaved: the input data sequence S and output data sequence S′ are formed by K/p partitions P each consisting of p data items. Preserving a pattern means that the ordering of the p data streams in each partition P is preserved after interleaving processing. Within a partition of size p, each data item belonging to a stream i, i={1, . . . , p} retains its rank after interleaving. The data item at the position i in the sequence after interleaving is obviously no longer the same, but belongs to the same stream i. This property is reflected in the fact that the difference between the position index of the interleaved data item and its rank in the interleaved sequence is a multiple of p, which can be expressed by the following equation:I(k)−k=Q(k)×p   (1)in which k={0, . . . , K−1} and Q(k) is a function in the relative integer space such that, whatever the value of k: Q(k)×p<K.
Thus a pattern of size p is preserved if equation (1) is satisfied: the difference between the position indices of rank k before and after interleaving is necessarily a multiple of the pattern of size p.
The interleaving law of an RP algorithm is given by the equation:I(k)=[s+kd]K where k={0, . . . , K−1}, d=|I(k+1)−I(k)|
The operation [X]K corresponds to the modulo K operation applied to X and therefore represents the remainder of the division of X by K, in other words:
            [      X      ]        K    =      X    -                  E        ⁡                  (                      X            K                    )                    ·      K      where E(z) is the integer part of z.
A restriction imposed by the algorithm is that K and d must be prime relative to each other. Consequently, only certain values of d are acceptable for a given size K and no value of d can correspond to the size of a pattern since pattern size is necessarily a sub-multiple of K. However, an analysis of different implementations of the algorithm shows that if d is chosen such that K is a multiple of d−1 then configurations exist for which a pattern of size p is preserved. In such circumstances, the quantity d−1 must be a multiple of p. This is reflected in the equation:K=n×(d−1)=n×m×p   (2)
In the situation where K=60, for example, the values of d such that K is a multiple of d−1 with d and K prime relative to each other are, for an interleaving spreading greater than 10: d=11, d=13 and d=31.
The interleaving laws RP associated with these three values of d for K=60 are presented in FIG. 1. For each of these situations, different patterns of size p satisfying equation (2) can be preserved. Thus, for d=13, it is possible to preserve a pattern of size p={3, 6, 12}. For d=31, it is possible to preserve a pattern of size p {3, 5, 6, 10}. Observation of the interleaving laws shows that a disadvantageous periodicity arises when the interleaving spreading d increases. Furthermore, the number of non-interleaved data items, i.e. the data items for which I(k)=k, increases with d.
Thus under certain conditions an RP algorithm effectively preserves a pattern of size p and fixes an interleaving spreading d of the data, but the values p and d must be low in order to limit the periodic structures and to limit the number of non-interleaved data items after interleaving.
If d−1 is not a sub-multiple of K then an RP algorithm cannot systematically preserve a pattern of size p, where K is a multiple of p. This is illustrated by the following example, with reference to FIG. 2: K=60 and d=23 (d−1=22 is not a sub-multiple of K). Consider a pattern of size p=3, chosen at random. Table 1 in Appendix 1 gives the quantity R′(k) corresponding to a pattern of size p=3, a value of d=23, a value of K=60, and the interleaving law of the RP technique:
            R      ′        ⁡          (      k      )        =                                          I            ⁡                          (              k              )                                -          k                3            ⁢                          ⁢              ∀        k              =          {              0        ,        …        ⁢                                  ,        59            }      
Because R′(k) has values in the real number space and not in the relative integer space, there is no systematic preservation of a pattern.
The preservation of the pattern by an RP algorithm advantageously enables simultaneous processing in a transmission system of interleaving intended to produce effects on a medium scale and interleaving intended to produce effects on a small scale (turbo-codes, interleaving within an OFDM symbol), and consequently optimizes the transmission system as a whole. However, the preservation of a pattern by an RP algorithm requires at least the parameter p to be prime relative to K, which can be regarded as a severe constraint.